package org.ymx.myHeap;

/**
 * 堆（优先队列）
 */

/**
 * 这里来分析T表示任意字符名，extends对泛型上限进行了限制即T必须是Comparable<? super T>的子类，
 * 然后<? super T>表示Comparable<>中的类型下限为T
 * <? extends T>：是指 “上界通配符（Upper Bounds Wildcards）”
 * <? super T>：是指 “下界通配符（Lower Bounds Wildcards）”
 *
 * @param <AnyType>
 */
public class MyHeap<AnyType extends Comparable<? super AnyType>> {


    public MyHeap() {
    }

    public MyHeap(int capacity) {
        AnyType[] anyTypes = (AnyType[]) new Comparable[capacity];
        new MyHeap(anyTypes);
        buildHeap();
    }

    public MyHeap(AnyType[] items) {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        for (AnyType anyType : items) {
            array[i++] = anyType;
        }
        buildHeap();
    }

    /**
     * 插入元素
     *
     * @param x
     */
    public void insert(AnyType x) {
        //扩容
        if (currentSize == array.length - 1) {
            enlargeArray(array.length * 2 - 1);
        }
        //上滤
        int hole = ++currentSize;
        for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }

    /**
     * 查看最小元素
     *
     * @return
     */
    public AnyType findMin() throws Exception {
        if (isEmpty()) throw new Exception("堆为空");
        return array[1];
    }

    /**
     * 删除最小元素
     *
     * @return
     */
    public AnyType deleteMin() throws UnderflowException, Exception {
        if (isEmpty()) {
            throw new UnderflowException();
        }
        AnyType minItem = findMin();
        array[1] = array[currentSize--];
        percolateDown(1);
        return minItem;
    }


    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void makeEmpty() {
        currentSize = 0;
    }

    //初始大小
    private static final int DEFAULT_CAPACITY = 10;
    //当前元素的个数
    private int currentSize;
    //全部元素
    private AnyType[] array;

    /**
     * 下滤
     *
     * @param hole
     */
    private void percolateDown(int hole) {
        int child;
        AnyType tmep = array[hole];
        //只要当前hole的左孩子小于size，即存在左孩子
        for (; hole * 2 <= currentSize; hole = child) {
            child = hole * 2;
            if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
                child++;
            }
            if (array[child].compareTo(tmep) < 0) {
                array[hole] = array[child];
            } else {
                break;
            }
        }
        array[hole] = tmep;
    }

    /**
     * 构建堆
     */
    private void buildHeap() {
        for (int i = currentSize; i > 0; i--) {
            percolateDown(i);
        }
    }

    private void enlargeArray(int newSize) {

    }
}
